package MonotoneStack;
/*
 * 柱状图中最大的矩形
 */
import java.util.Deque;
import java.util.LinkedList;

public class lc84 {

    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new LinkedList<>();
        int len = heights.length + 2;
        int[] newheights = new int[len];
        newheights[0] = 0;
        newheights[len - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newheights[index + 1] = heights[index];
        }
        heights = newheights;
        stack.push(0);
        int res = 0;
        for (int i = 1; i < len; i++) {
            if (heights[i] > heights[stack.peek()]) {
                stack.push(i);
            } else if (heights[i] == heights[stack.peek()]) {
                stack.pop();
                stack.push(i);
            } else {
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    int mid = stack.pop();
                    int left = stack.peek();
                    int right = i;
                    int h = heights[mid];
                    int w = right - left - 1;
                    res = Math.max(res, h * w);
                }
            }
            stack.push(i);
        }
        return res;
    }

}
